On Revenue Monotonicity in Combinatorial Auctions

摘要

Along with substantial progress made recently in designing near-optimalmechanisms for multi-item auctions, interesting structural questions have alsobeen raised and studied. In particular, is it true that the seller can alwaysextract more revenue from a market where the buyers value the items higher thananother market? In this paper we obtain such a revenue monotonicity result in ageneral setting. Precisely, consider the revenue-maximizing combinatorialauction for $m$ items and $n$ buyers in the Bayesian setting, specified by avaluation function $v$ and a set $F$ of $nm$ independent item-typedistributions. Let $REV(v, F)$ denote the maximum revenue achievable under $F$by any incentive compatible mechanism. Intuitively, one would expect that$REV(v, G)\geq REV(v, F)$ if distribution $G$ stochastically dominates $F$.Surprisingly, Hart and Reny (2012) showed that this is not always true even forthe simple case when $v$ is additive. A natural question arises: Are thesedeviations contained within bounds? To what extent may the monotonicityintuition still be valid? We present an {approximate monotonicity} theorem forthe class of fractionally subadditive (XOS) valuation functions $v$, showingthat $REV(v, G)\geq c\,REV(v, F)$ if $G$ stochastically dominates $F$ under $v$where $c>0$ is a universal constant. Previously, approximate monotonicity wasknown only for the case $n=1$: Babaioff et al. (2014) for the class of additivevaluations, and Rubinstein and Weinberg (2015) for all subaddtive valuationfunctions.